
class LinkedList:
    '''
        链表(单链表)，带index
    '''
    class LNode:
        '''链表节点'''
        def __init__(self, value=None, _next=None):
            self.data = value
            self.next = _next

    def __init__(self,lst=None):
        if isinstance(lst, list):  #列表转链表
            self.size = len(lst)
            LN=self.LNode(lst[-1])
            for x in range(self.size-1):
                N=self.LNode(lst[self.size-2-x],LN)
                LN=N
            self.head = self.LNode(self.size,LN)
        else:
            self.head = self.LNode(0) #head:头指针
            self.size = 0 #len()

    def __len__(self):
        return self.size
    def __getitem__(self, index):
        return self.get(index)
    def __setitem__(self, key, value):
        self.set(key, value)
    def __contains__(self, value):
        return self.contains(value)
    def __delitem__(self, index):
        self.pop(index)
    def __str__(self):
        return f'LinkedList({self.size}):{self.list()}'

    def is_empty(self):
        return self.size == 0

    def insert(self, index, value):
        if index < 0 or index > self.size:
            raise IndexError(f'Add failed, Required index >= 0 and index <= {self.size}')
        # 找到要插入的位置的前一个节点
        pre = self.head
        for i in range(index):
            pre = pre.next
        add_node = self.LNode(value=value)
        add_node.next = pre.next
        pre.next = add_node
        self.head.data += 1
        self.size += 1

    def add(self, value):
        self.insert(self.size, value)

    def get(self, index):
        if self.size == 0:
            raise IndexError("linked_list is empty")
        if index < 0 or index >= self.size:
            raise IndexError(f'Add failed, Required index >= 0 and index <= {self.size}')
        cur = self.head
        for i in range(index + 1):
            cur = cur.next
        return cur.data

    def set(self, index, value):
        if self.size == 0:
            raise IndexError("linked_list is empty")
        if index < 0 or index >= self.size:
            raise IndexError(f'Set failed, Required index >= 0 and index <= {self.size}')
        cur = self.head
        for i in range(index + 1):
            cur = cur.next
        cur.data = value

    def contains(self, value):
        cur = self.head.next
        for i in range(self.size):
            if cur.data == value:
                return True
            cur = cur.next
        return False

    def pop(self, index=None):
        '''
            删除链表中索引为index位置的节点，并返回节点的值
        '''
        if index==None : index=self.size-1
        if self.size == 0:
            raise IndexError("linked_list is empty")
        if index < 0 or index >= self.size:
            raise IndexError(f'Remove failed, Required index >= 0 and index <= {self.size}')
        pre = self.head
        for i in range(index):
            pre = pre.next
        remove_node = pre.next
        ret = remove_node.data
        pre.next = remove_node.next
        remove_node.next = None
        self.head.data -= 1
        self.size -= 1
        return ret

    def remove(self, value):
        '''
            删除链表中值为value的节点
        '''
        cur = self.head
        for i in range(self.size):
            if cur.next is not None:
                cur = cur.next
                if cur.data == value:
                    self.pop(i)
                    break
        else:
            raise ValueError(f'The node whose value is {value} does not exist')

    def list(self): #tolist
        lst=[]
        ln=self.head.next
        while ln:
            lst.append(ln.data)
            ln=ln.next
        return lst



if __name__ == "__main__":
    l1=LinkedList([1,2,3,4,5,6])
    l2=LinkedList()
    l2.add(3)
    print(l1,l2)

    l1.insert(2,87)
    l1.remove(3)
    l1.pop()
    print(l1)

    l2.insert(0,4)
    l2[1]=56
    print(l2,l2[0])